package 回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * 22. 括号生成
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
    要解决生成有效括号组合的问题，我们可以使用回溯算法来系统地探索所有可能的组合，并通过剪枝来确保生成的每个组合都是有效的。
 以下是详细的解题思路和代码实现：
    解题思路：
    1. 有效的括号：生成的括号字符串必须要满足以下两个条件：
        左括号和右括号的数量相等；
        在任意前缀中，左括号的数量必定不少于右括号的数量
    2: 回溯法：通过递归构建所有可能的字符串，并在每一步决策时确保满足上述条件：
        当左括号的数量小于n时，可以添加左括号；
        当右括号的数量小于左括号的数量时，可以添加右括号；
    3：递归终止条件：
        当字符串长度达到2n时，将其加入结果列表；
 */
public class L_22 {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result,"",0,0,n);
        return result;
    }

    private void backtrack(List<String> result,String current,int left,int right,int n){
        // 终止条件：当字符串长度达到2n时，将其加入结果列表
        if(current.length() == 2 * n){
            result.add(current);
            return;
        }
        // 如果左括号的数量小于n，可以添加左括号
        if (left < n){
            backtrack(result,current+'(',left+1,right,n);
        }
        // 如果右括号的数量小于左括号，才可以添加右括号
        if (right < left){
            backtrack(result,current+')',left,right+1,n);
        }
    }
}
